home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 February: Tool Chest / Apple Developer CD Series Tool Chest February 1996 (Apple Computer)(1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / MacMarlais 0.5.9d46 / Examples / fib-memo.dyl < prev    next >
Encoding:
Text File  |  1995-03-13  |  986 b   |  45 lines  |  [TEXT/Mrls]
  1. /*
  2.     fib-memo.dyl
  3.     
  4.     Example of memoization in Dylan.
  5.     
  6.     Credits to Bruce@hoult.actrix.gen.nz (Bruce Hoult) for add-method approach.
  7.     <table> version by Patrick C. Beard <beard@cs.ucdavis.edu>.
  8.  */
  9.  
  10. define method fib-memo (n == 0) 1 end;
  11. define method fib-memo (n == 1) 1 end;
  12.  
  13. define method fib-memo (n :: <integer>)
  14.     let f = fib-memo (n - 2) + fib-memo (n - 1);
  15.     add-method (fib-memo, method (n == n) f end);
  16.     f
  17. end;
  18.  
  19. // alternate approach.
  20.  
  21. define constant $fib-memo-table$ = make (<table>);
  22. $fib-memo-table$[0] := 1;
  23. $fib-memo-table$[1] := 1;
  24.  
  25. define method fib-table (n :: <integer>)
  26.     let f = element ($fib-memo-table$, n, default: #f);
  27.     if (~f)
  28.         f := fib-table (n - 2) + fib-table (n - 1);
  29.         $fib-memo-table$[n] := f;
  30.     end if;
  31.     f
  32. end method;
  33.  
  34. define method memoize (f :: <function>)
  35.     let f-table = make (<table>);
  36.     method (n :: <integer>)
  37.         let value = element (f-table, n, default: #f);
  38.         if (~value)
  39.             value := f (n);
  40.             f-table[n] := value;
  41.         end if;
  42.         value
  43.     end
  44. end method;
  45.